import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by L.jp
 * Description:给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 *
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 *
 * 你可以按任意顺序返回答案。

 * User: 86189
 * Date: 2023-03-14
 * Time: 1:16
 */
public class Solution {
    public static int[] twoSum(int[] nums, int target) {
        //哈希表法
        /*HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int num=target-nums[i]; //逆向思维，做减法
            //查看哈希表是否有这个数
            if(map.containsKey( num )){
                //如果存在这个差值，就返回这两个数
                return new int[]{i,map.get( num )};
            }
            //哈希表不包含的话就把数值作为key,索引作为val,构建哈希表
            map.put( nums[i],i );
        }
        //两个数不存在
        return null;*/
        
        //双指针法，需要借助另外一个二维数组
        int n=nums.length;
        //先复制一份数组.n代表有几个数，2代表数组存储元素和下标两个元素
        int[][] copy=new int[n][2];
        for(int i = 0; i < n; i++){
            copy[i][0]=nums[i];
            copy[i][1]=i;
        }
        //先排序，有序之后可以减少重复的搜索，我们排序之后返回的下标应该是原来数组的下标，不是排序后的数组下标，所以应该使用新的数组
        /*Arrays.sort(copy, (ni1, ni2) -> {
            return ni1[0] == ni2[0] ? ni1[1] - ni2[1] : ni1[0] - ni2[0];
        });*/
        Arrays.sort( copy , new Comparator<int[]>() {
            @Override
            public int compare (int[] o1 , int[] o2) {
                //如果数值相等，那么按照下标排序，否则按照数值排序
                return o1[0]==o2[0] ? o1[1]-o2[1] : o1[0]-o2[0];
            }
        } );
        //双指针
        int left=0;
        int right=copy.length - 1;
        while (left < right) {
            int sum=copy[left][0]+copy[right][0];
            if(sum>target){
                //右边数值偏大
                right--;
            }else if(sum<target) {
                left++;
            }else {
                return new int[]{copy[left][1],copy[right][1]};
            }
        }
        return new int[]{};
    }
    
    public static void main (String[] args) {
        int nums[]={3,2,4};
        int target=6;
        System.out.println( Arrays.toString( twoSum( nums , target ) ) );
    }

}
